1. Field of the Invention
Example embodiments of the present invention relate generally to a method of sending data, and, more particularly, to a method of sending data from a source node to a destination node.
2. Description of the Related Art
Ad-hoc On-demand Distance Vector (AODV) protocol is a method of routing messages between mobile devices. It allows these mobile devices, or nodes, to pass messages through their neighbors to nodes with which they cannot directly communicate. AODV does this by discovering the route(s) along which messages can be passed. AODV makes sure these routes do not contain loops (e.g., one or more Nodes which repeat) and tries to find the shortest route possible (e.g., based on delay, a number of visited Nodes or hops, etc.). AODV is also able to handle changes in routes and can create new routes if there is an error.
FIG. 1 illustrates a conventional AODV network 100. As shown in FIG. 1, the AODV network 100 includes Nodes 1, 2, 3, 4 and 5 with coverage areas 105, 110, 115, 120 and 125, respectively. Nodes which can communicate directly with other Nodes are referred to as “neighbors”.
Each Node in the AODV network 100 keeps track of its neighbors by listening for “HELLO” messages that every Node broadcasts at fixed, periodic intervals. When a given Node desires to send a message to a non-neighbor Node, the Node broadcasts a Route Request (RREQ) message. The RREQ message includes a source identifier identifying the Node sending the RREQ message, a destination identifier identifying the non-neighbor Node to which the message is addressed, a lifespan of the message and a Sequence Number serving as a unique identifier for the message. The lifespan indicates a duration that the message is “active”, after which no attempts to transfer the message to the destination non-neighbor Node will be performed by any Node.
FIG. 2 illustrates a conventional message routing process within the AODV network 100 of FIG. 1. In step S200, Node 1 determines to send a message to Node 3. As shown in FIG. 1, Node 1's neighbors are Nodes 2 and 4. Therefore, Node 1 cannot directly communicate with Node 3. Node 1 broadcasts a RREQ, which is received by Node 4 and Node 2. In this example, for the sake of simplicity, the destination identifier is “3” (i.e., to designate Node 3), the source identifier is “1” (i.e., to designate Node 1), the Lifespan is “3” (e.g., to designate a time duration, such as 3 seconds or 3 hops) and the Sequence Number is “0”. Thus, the RREQ sent by the Node 1 may be expressed as [Destination identifier, Source identifier, Lifespan, Sequence Number] or [3, 1, 3, 0].
The RREQ [3, 1, 3, 0] is received by each of neighbor Nodes 2 and 4. In steps S205 and S210, Nodes 4 and 2, respectively, determine whether the destination identifier identifies a Node that is (i) known by Nodes 4 or 2, respectively or (ii) whether the receiving Node (e.g., Node 2 or 4) is identified by the destination identifier. If each of conditions (i) and (ii) are not met, the receiving Node rebroadcasts the received RREQ if the lifespan has not expired. Accordingly, in step S205, since Node 4 is not Node 3's neighbor and Node 4 is not Node 3, Node 4 rebroadcasts the RREQ, which is received by Node 5. It is understood that because Node 1 is Node 4's neighbor, Node 1 would also receive the RREQ, but because Node 1 is the original sending Node, this step has not been illustrated because the receipt of the rebroadcast RREQ would be ignored by Node 1. Also, while not shown, step S205, performed at Node 4, would then be performed at Node 5 after receiving the rebroadcast RREQ from Node 4, and so on.
Returning to step S210, Node 2 is a neighbor of Node 3 and therefore knows the route to Node 3. Node 2 then determines whether Node 2 is the Node identified by the destination identifier. Because Node 2 is not the destination entity, Node 2 sends a Route Reply (RREP) back to the Node 1 to indicate that a route to Node 3 has been found and also rebroadcasts the RREQ to Node 3. RREPs are similar to RREQs, but RREPs include a hop count (i.e., a number of Nodes separating the source or sending Node to the receiving or destination Node, e.g., Node 1 to Node 3 includes 2 hops) in place of the lifespan.
Node 3 receives the rebroadcast RREQ and determines whether conditions (i) and (ii) are met in step S215. Because condition (ii) is met (i.e., Node 3 is the Node identified by the destination identifier), Node 3 sends a RREP to Node 1 through Node 2 and does not rebroadcast the RREQ.
Node 1 receives the RREP from Node 3 and determines, based on the RREP's Sequence Number, whether to update a routing path to Node 3. Sequence numbers serve as time stamps by allowing Nodes to determine how “fresh” their information is with respect to other Nodes. Each time a Node sends a new message, the Sequence Number associated with the new message is incremented from a previously sent message. Each Node records the current (i.e., highest) Sequence Number of the Nodes it talks to. Higher Sequence Numbers indicate “fresher” or more up-to-date routes.
Referring to FIGS. 1 and 2, Node 1 forwards the RREP received from Node 3 to Node 4, which is forwarded to Node 5, and so on. Node 1 compares the received RREP with a stored route to Node 3 and determines that the RREP's Sequence Number is higher than its stored route. Accordingly, Node 1 updates its stored route with the route indicated by the RREP in step S225. Alternatively, the newly determined route is added as an alternate routing path, such that multiple routing paths are available from Node 1 to Node 3.
Once a routing path from a source Node to a destination Node is known, the source Node sends data to the destination Node until a Route Error Message (RERR) is received. The RERR indicates a broken link in one or more routing paths between the source Node to the destination Node. Whenever a Node receives a RERR, the Node examines its Routing Table and removes all the routes that contain the “bad” Nodes (i.e., the Nodes to which the source Nodes are no longer connected, at least through the old routing path).
Generally, a RERR is broadcast in response to three (3) situations. In a first scenario, a Node receives a data packet for forwarding but does not have a routing path to the data packet's destination. Thus, another Node (i.e., sending the data packet) erroneously thinks a correct routing path to the destination Node is through the Node not knowing the destination.
In a second scenario, a Node receives a RERR that causes at least one of its Routes to become invalidated. The Node sends out a RERR with all the new Nodes which are now unreachable. In a third scenario, the Node detects that it cannot communicate with one of its neighbors. The Node updates its route table to invalidate routes using the unreachable neighbor as a first hop. Then, the Node sends out a RERR indicating the neighbor is not connected, which invalidates those associated routing paths.
Traditional router vendors use a Command Line Interface (CLI) to support routing protocols which are implemented within various kinds of networks, such as the Internet. A CLI is a type of user interface to a computer's operating system or an application in which the user responds to a visual prompt by typing in a command on a specified line, receives a response back from the system, and then enters another command, and so forth. For example, the MS-DOS Prompt application in a Windows operating system is a CLI provision. The CLI permits a network manager to view statistics, make configuration changes and perform other administrative functions.
Router venders typically employ protocols which are best for the integrity of the system. Router vender protocols typically take into account administrative distance. Administrative distance is the feature used by routers to select a best path when there are two or more different routing paths from a given Node to the same destination using different routing protocols. Administrative distance defines the reliability of a routing protocol. Each routing protocol is prioritized by the router in order of most to least reliable using an administrative distance value.
For example, the CLI used by a router vender may be:
Ip route 192.0.0.0 255.0.0.0 135.252.20.1 120 such that all packets received from 192.0.0.0/255.0.0.0 are routed to router 135.252.20.1 if a path between a source Node and a destination Node, associated with an administrative distance value less than an administrative distance threshold (e.g., 120), is not available. For critical systems, such router-defined parameters support conservative protocols which protect the system. However, end users, which are in fact “hosts” in AODV networks, are not allowed to select between available paths, and instead are at the mercy of the protocols defined by the router venders.